//      优先级队列（堆)

import java.util.Arrays;

//      存储方式 使用数组保存二叉树结构，
//      将二叉树用层序遍历方式放入数组中。一般只适合表示完全二叉树，因为非完全二叉树会有空间的浪费。
//      堆概念：
//      1. 堆逻辑上是一棵完全二叉树
//      2. 堆物理上是保存在数组中
//      3. 满足任意结点的值都大于其子树中结点的值，叫做大堆，或者大根堆，或者最大堆
//      4. 反之，则是小堆，或者小根堆，或者最小堆
//      5. 堆的基本作用是，快速找集合中的最值
public class TestHeap {


//    将一颗二叉树调整为大根堆
//    1、调整是从最后一棵子树出发的
//    2、每棵子树的调整都是向下调整的
//      1、如何找到最后一棵子树。
//      (len- 1)-->child
//      parent=((len-1)-1)/ 2;
//      2、parent-- 就可以遍历完每棵子树了
//      3、最主要的问题就是写一个向下调整的函数即可
//      4、每棵树的调整结束位置，如何判定
//          每棵树调整的结束位置实际上都是一样的

    public int[] elem;
    public int usedSize;

    public TestHeap() {
        this.elem = new int[10];
    }



    public void createBigHeap(int[] array) {
//        将数组保存起来 相当于拷贝一份
        for (int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            this.usedSize++;
        }

//        向下调整 （最后一个孩子的parent开始）
//            建立堆的   时间复杂度看代码是O(N*log(2)N)  实际上是O(N)   堆10  2:00
        for (int parent = ((this.usedSize-1)-1)/2; parent >= 0; parent--) {
            shiftDown(parent, this.usedSize);
        }
    }

    /**
     *向下调整
     * @param parent 开始位置
     * @param len   结束位置
     */
    public void shiftDown(int parent, int len) {
        int child = parent*2+1;
//        最起码有左孩子  至少有一个孩子
        while (child < len) {
//            有右孩子
            if (child+1 < len && elem[child] < elem[child+1]) {
                child++;//保证当前左右孩子最大值下标
            }
//            如果 看是否需要交换parent 和 child 的值
            if (elem[parent] < elem[child]) {
                int tmp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = tmp;

//                不知道向下交换的值 在下一个双亲节点是不是最大的 还要进行 向下调整
                parent = child;
                child = parent*2+1;
            }else {
                break;//如果没有交换 就结束 因为下面的双亲节点 已经是最大树了
            }
        }
    }





    public void offer(int val) {
        if (isFull()) {
//            扩容
            this.elem = Arrays.copyOf(this.elem,2*elem.length);
        }
        elem[usedSize] = val;
        usedSize++;
//        拿到最后一个元素的下标
        shiftUp(usedSize-1);
    }
    public boolean isFull() {
        return this.elem.length == this.usedSize;
    }
//    向上调整
    public void shiftUp(int child) {
        int parent = (child-1)/2;
        while (child > 0) {
            if (elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                child = parent;
                parent = (child-1)/2;
            }else {
                break;
            }
        }

    }



//      删除头结点（队列）
    public int poll() {
        if (isEmpty()) {
            throw new RuntimeException("优先级队列为空");
        }
        int tmp = elem[0];
        elem[0] = elem[this.usedSize-1];
        elem[this.usedSize-1] = tmp;
        this.usedSize--;
        shiftDown(0,this.usedSize);
        return tmp;
    }
    public boolean isEmpty() {
        return this.usedSize == 0;
    }

//    查看头结点
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("优先级队列为空");
        }
        return this.elem[0];
    }








//    练习

//    问题：在许多数中找前 K 个最大的，要建 K 个大小的小堆
//    思路一：排序
//    思路二：创建堆    时间复杂度n*log(2)n
//    思路三：只找topk 不排序
//    时间复杂度n*log(2)k   k是高度  n是(遍历一遍)元素的个数
//      1、先把前3个元素，创建为小根堆。
//      2、当前的堆为什么是小根堆，因为堆顶的元素，一定是当前K个元素当中最小的一个元素。
//      如果，有元素X比堆顶元素大，那么X这个元素，可能就是topk中的一个。
//      相反如果是大根堆，那就不一定了
//      3、如果堆顶元素小，那么出堆顶元素，然后入当前比堆顶大的元素再次调整为小根堆
//
//    总结：
//    1.如果求前k个最大的元素，要建一个小根堆
//    2.如果求前k个最小的元素，要建一个大根堆
//    3.第k大的元素 建一个小堆 堆顶元素就是第k大的元素
//    4.第k小的元素 建一个大堆 堆顶元素就是第k小的元素


//    问题：对一组数据进行从小到大的排序 借助大根堆 还是 小根堆
//    大根堆
//    思路:
//    1.调整为大根堆
//    2.0下标和最后一个未排序的元素进行交换即可
//    3.end--
    public void heapSort() {
        int end = this.usedSize-1;
        while (end > 0) {
            int tmp = this.elem[0];
            this.elem[0] = this.elem[end];
            this.elem[end] = tmp;
            shiftDown(0,end);//这里是end 因为交换后最后一个值已经是最大的了 使用不需要再进行大根堆排序
            end--;
        }
    }
}
